package cn.zzf.algs.note.exercise.sort;

import cn.zzf.algs.note.base.sort.Sort;
import cn.zzf.algs.note.base.util.SortUtil;

/**
 * 实现链表的归并排序，使用fast-slow方法，对一个无序的链表进行排序，时间复杂度O(n), 空间复杂度O(1)
 * @author GaoFeng2017
 * @date 2020/7/28 19:45
 */
public class Ex_2_2_17_LinkedListSortV2 implements Sort {

    /** 结点对象信息 */
    private class Node {

        Comparable value;
        Node next;

        public Node(Comparable value, Node next) {
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {

            StringBuilder result = new StringBuilder();
            Node currentNode = this;
            result.append("[");

            while (currentNode != null) {
                result.append(currentNode.value).append(", ");
                currentNode = currentNode.next;
            }

            result.delete(result.length() - 2, result.length());
            result.append("]");

            return result.toString();

        }

    }

    @Override
    public void sort(Comparable[] elements) {

        if (elements == null || elements.length <= 1) {
            return;
        }

        // 7 6 5 4 3 2 1
        // 将数组转为链表
        Node firstNode = this.createLinkedList(elements);
        Node beginNode = firstNode;
        Node middleNode = firstNode;
        Node endNode = firstNode;
        Node beginNodeOfLastMerge = firstNode;

        int numberOfSubList;
        // System.out.println(firstNode);

        do {
            numberOfSubList = 0;
            while (endNode.next != null) {
                if (SortUtil.less(endNode.next.value, endNode.value)) {
                    // 第一个有序子链表已找到
                    if ((numberOfSubList &  1) == 1) {
                        // System.out.println("firstNode:" + firstNode);
                        if (beginNode == firstNode) {
                            // 第一次合并，得到新的链表头，后续的排序结点都基于该链表头
                            firstNode = this.merge(beginNode, middleNode, endNode);
                        } else {
                            beginNode.next = this.merge(beginNode.next, middleNode, endNode);
                        }

                        beginNodeOfLastMerge = beginNode;
                        beginNode = endNode;
                        middleNode = endNode;
                        // System.out.println("after merge, beginNode:" + firstNode);
                    } else {
                        // 更新mid的位置和查找状态
                        middleNode = endNode;
                        beginNodeOfLastMerge = beginNode;
                    }
                    numberOfSubList++;
                }
                endNode = endNode.next;
            }

            // 1.链表内只有两个元素: 2 1
            // 2.链表剩下两个有序的子链表: 5 6 7 8 1 2 3 4
            // 3.前面N个已合并的元素，同时最后一个子链表是自然有序的:  12 13 14 1 2 3 4
            // 4.前面N个已合并的子链表，剩余1个未合并的子链表: 4 5 6 9 10 11 2
            // 5.前面N个已合并的元素和一个未合并的元素以及一个元素的子链表: 4 5 6 3 10 18 14 13 15
            // 6.链表第一个有序的子链表只有1个元素，剩下的子链表都是有序的。

            // 合并剩余的最后一链表（可能为一个元素，也可能是多个有序的元素）
            // beginNode: firstNode (1,2,6) or endNode.next (3,4,5)
            // middleNode: middleNode (3,4,5) or beginNode (1,2,6)
            // endNode: endNode (1-6)

            if (numberOfSubList > 0) {
                if (beginNodeOfLastMerge == firstNode) {
                    firstNode = this.merge(firstNode, middleNode, endNode);
                } else {
                    beginNodeOfLastMerge.next = this.merge(beginNodeOfLastMerge.next, middleNode, endNode);
                }
            }

            // System.out.println("<<<< break inner loop, numberOfSubList:" + numberOfSubList + " >>>>");

            beginNode = firstNode;
            endNode = firstNode;

        } while (numberOfSubList > 0);

        // System.out.println("after sort, firstNode: " + firstNode);

        // 复制元素到子数组
        for (int i = 0; i < elements.length; i++) {
            elements[i] = firstNode.value;
            firstNode = firstNode.next;
        }

    }


    /** 选择排序 */
    private void selectionSort() {

    }

    /** 插入排序, 复杂度 为O(n^2)  */
    private void insertionSort(Comparable[] elements) {
        for (int i = 1; i < elements.length; i++) {
            for (int j = i; j > 0 && SortUtil.less(elements[j - 1], elements[j]); j--) {
                SortUtil.exchange(elements, j,  j - 1);
            }
        }
    }



    private void selfTest() {
        // [512, 116, 53, 368, 534, 531, 374]
        // step-1 firstNode: 512, beginNode: 512, middleNode: null, endNode: 512, numberOfSubList: 0
        // in loop-1
        // step-2 firstNode: 512, beginNode: 512, middleNode: null -> 512, endNode: 512, numberOfSubList: 1
        // in loop-2 start merge
        // step-3 firstNode: 512, beginNode: 512, middleNode: 512, endNode: 512 -> 116, numberOfSubList: 1
        // step-4 lastNodeOfrResultList: null, resultList: null, leftNode: 512, rightNode: 116, endNode: 116
        // trigger SortUtil.less(rightNode.value, leftNode.value) case
        // step-5 lastNodeOfResultList: 116, resultList: 116, rightNode: 116 -> 53, leftNode: 512
        // skip leftNode != middleNode.next && rightNode != endNode.next case, trigger leftNode == middleNode.next else case
        // step-6 lastNodeOfResultList: 116, lastNodeOfResult.next: 53 -> 512, middleNode: 512, middleNode.next: 116 -> 53, resultList: 116, rightNode: 116 -> 53, leftNode: 512
        // step-7 firstNode: 116 -> 512 -> 53 -> 368, beginNode: 512 -> 116, middleNode: 512, endNode: 116 -> 53, numberOfSubList: 2
    }


    /** 合并两个有序的子链表 */
    private Node merge(Node beginNode, Node middleNode, Node endNode) {

        // 合并后的头
        Node resultList = null;
        Node lastNodeOfResultList = null;
        Node leftNode = beginNode;
        Node rightNode = middleNode.next;

        // 初始化合并后链表的头
        if (SortUtil.less(rightNode.value, leftNode.value)) {
            lastNodeOfResultList = rightNode;
            rightNode = rightNode.next;
        } else {
            lastNodeOfResultList = leftNode;
            leftNode = leftNode.next;
        }

        /*System.out.println("==== start merge ==== \nbeginNode:" + beginNode + "\nmiddleNode:" + middleNode
                + "\nendNode:" + endNode + "\nlastNodeOfResultList" + lastNodeOfResultList
                + "\nleftNode:" + leftNode + "\nrightNode:" + rightNode);*/

        // 合并结果链表的表头
        resultList = lastNodeOfResultList;

        while (leftNode != middleNode.next && rightNode != endNode.next) {
            if (SortUtil.less(rightNode.value, leftNode.value)) {
                lastNodeOfResultList.next = rightNode;
                lastNodeOfResultList = rightNode;
                rightNode = rightNode.next;
            } else {
                lastNodeOfResultList.next = leftNode;
                lastNodeOfResultList = leftNode;
                leftNode = leftNode.next;
            }
        }

        // 连接剩下未排序的链表
        if (leftNode == middleNode.next) {
            // 直接连接，不用跳过左结点，因为右节点在左结点之后
            lastNodeOfResultList.next = rightNode;
        } else {
            // 19 23 223 19 23 -> 19 ...
            // 跳过已经取完的右节点, 不能放在下面语句的下面，否则会循环引用
            middleNode.next = endNode.next;
            // 连接左链表，同时将middle结点指向high.next
            lastNodeOfResultList.next = leftNode;
        }

        /*System.out.println("resultList: " + resultList);
        System.out.println("==== end merge ====");*/

        return resultList;
    }


    private Node createLinkedList(Comparable[] elements) {
        Node result = null;
        for  (int i = elements.length - 1; i >= 0; i--) {
            // 将链表节点初始化
            result = new Node(elements[i], result);
        }
        return result;
    }

}
